{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 第2章 感知机"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "&emsp;&emsp;感知机（preceptron）是根据输入实例的特征向量 $x$ 对其进行二类分类的线性分类模型：\r\n",
    "$$f(x)=\\operatorname{sign}(w \\cdot x+b)$$\r\n",
    "感知机对应于输入空间（特征空间）中的分离超平面 $w \\cdot x+b=0$，属于判别模型。\r\n",
    "\r\n",
    "&emsp;&emsp;感知机学习的策略是极小化损失函数：\r\n",
    "$$\\min _{w, b} L(w, b)=-\\sum_{x_{i} \\in M} y_{i}\\left(w \\cdot x_{i}+b\\right)$$\r\n",
    "损失函数对应于误分类点到分离超平面的总距离。\r\n",
    "\r\n",
    "&emsp;&emsp;感知机学习算法利用随机梯度下降法对损失函数进行极小化，具有简单且易于实现的优点，分为原始形式和对偶形式。\r\n",
    "\r\n",
    "&emsp;&emsp;当训练数据集线性可分时，感知机学习算法是收敛的，存在无穷多个解，其解由于不同的初值或不同的迭代顺序而可能有所不同。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 算法"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\r\n",
    "import matplotlib.pyplot as plt"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 算法2.1 感知机学习算法的原始形式\r\n",
    "&emsp;&emsp;输入：训练数据集 $T=\\{(x_1, y_1), (x_2, y_2), \\cdots, (x_N, y_N)\\}$，其中 $x_i ∈ \\mathcal{X}=R^n$，$y_i∈\\mathcal{Y}=\\{-1, +1\\}$，$i=1, 2, \\cdots, N$；学习率 $η\\ (0<η\\le1)$；\r\n",
    "\r\n",
    "&emsp;&emsp;输出：$w,b$；感知机模型 $f(x)=\\operatorname{sign}(w\\cdot x+b)$\r\n",
    "\r\n",
    "&emsp;&emsp;（1）选取初值 $w_0, b_0$；\r\n",
    "\r\n",
    "&emsp;&emsp;（2）在训练集中选取数据 $(x_i, y_i)$；\r\n",
    "\r\n",
    "&emsp;&emsp;（3）如果 $y_i(w\\cdot x_i+b)\\le 0$，\r\n",
    "$$w←w+ηy_ix_i$$\r\n",
    "$$b←b+ηy_i$$\r\n",
    "&emsp;&emsp;（4）转至（2），直至训练集中没有误分类点。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Preceptron:\r\n",
    "    def __init__(self, eta=1e-2, max_iter=1e4, shuffle=False, verbose=False):\r\n",
    "        self.eta = eta\r\n",
    "        self.max_iter = max_iter\r\n",
    "        self.shuffle = shuffle\r\n",
    "        self.verbose = verbose\r\n",
    "    \r\n",
    "    def sign(self, x):\r\n",
    "        return 1 if np.dot(x, self.w) + self.b >= 0 else -1\r\n",
    "\r\n",
    "    def fit(self, X, Y):\r\n",
    "        self.w = np.zeros(X.shape[-1])\r\n",
    "        self.b = 0\r\n",
    "\r\n",
    "        n_iter = 0\r\n",
    "        wrong = 1\r\n",
    "\r\n",
    "        while wrong > 0 and n_iter < self.max_iter:\r\n",
    "            wrong = 0\r\n",
    "            if self.shuffle:\r\n",
    "                index = np.random.permutation(X.shape[0])\r\n",
    "            else:\r\n",
    "                index = np.arange(X.shape[0])\r\n",
    "            for i in index:\r\n",
    "                x, y = X[i], Y[i]\r\n",
    "                if y * (np.dot(x, self.w) + self.b) <= 0:\r\n",
    "                    self.w += self.eta * y * x\r\n",
    "                    self.b += self.eta * y\r\n",
    "                    wrong += 1\r\n",
    "                    n_iter += 1\r\n",
    "\r\n",
    "                    if self.verbose:\r\n",
    "                        print('Iteration {} samples x{} was misclassified, w = {}, b = {}'.format(n_iter, i + 1, self.w, self.b))\r\n",
    "\r\n",
    "        print('Finished at iteration {}, w = {}, b = {}'.format(n_iter, self.w, self.b))\r\n",
    "    \r\n",
    "    def predict(self, X):\r\n",
    "        return np.apply_along_axis(self.sign, axis=-1, arr=X)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 算法2.2 感知机学习算法的对偶形式\r\n",
    "&emsp;&emsp;输入：训练数据集 $T=\\{(x_1, y_1), (x_2, y_2), \\cdots, (x_N, y_N)\\}$，其中 $x_i∈\\mathcal{X}=R^n$，$y_i∈\\mathcal{Y}=\\{-1, +1\\}$，$i=1, 2, \\cdots, N$；学习率 $η\\ (0<η\\le1)$；\r\n",
    "\r\n",
    "&emsp;&emsp;输出：$\\alpha,b$；感知机模型 $f(x)=\\operatorname{sign}\\left(\\sum_{j=1}^N\\alpha_jy_jx_j\\cdot x+b\\right)$，其中 $\\alpha=(\\alpha_1,\\alpha_2,\\cdots,\\alpha_N)^T$。\r\n",
    "\r\n",
    "&emsp;&emsp;（1）$\\alpha←0, b←0$；\r\n",
    "\r\n",
    "&emsp;&emsp;（2）在训练集中选取数据 $(x_i, y_i)$；\r\n",
    "\r\n",
    "&emsp;&emsp;（3）如果 $y_i\\left(\\sum_{j=1}^N\\alpha_jy_jx_j\\cdot x_i+b\\right)\\le0$，\r\n",
    "$$\\alpha_i←\\alpha_i+η$$\r\n",
    "$$b←b+ηy_i$$\r\n",
    "&emsp;&emsp;（4）转至（2），直至训练集中没有误分类点。\r\n",
    "\r\n",
    "&emsp;&emsp;对偶形式中训练实例仅以内积的形式出现。为了方便，可以预先将训练集中的实例间的内积计算出来并以矩阵的形式存储，即 Gram 矩阵：\r\n",
    "$$G=[x_i\\cdot x_j]_{N\\times N}$$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Preceptron_dual:\r\n",
    "    def __init__(self, eta=1e-2, max_iter=1e4, shuffle=False, verbose=False):\r\n",
    "        self.eta = eta\r\n",
    "        self.max_iter = max_iter\r\n",
    "        self.shuffle = shuffle\r\n",
    "        self.verbose = verbose\r\n",
    "    \r\n",
    "    def alpha2w(self, X, Y):\r\n",
    "        return np.sum((self.alpha * Y * X.T).T, axis=0)\r\n",
    "\r\n",
    "    def sign(self, x):\r\n",
    "        return 1 if np.dot(x, self.w) + self.b >= 0 else -1\r\n",
    "    \r\n",
    "    def gram_matrix(self, X):\r\n",
    "        return np.dot(X, X.T)\r\n",
    "\r\n",
    "    def fit(self, X, Y):\r\n",
    "        self.alpha = np.zeros(X.shape[0])\r\n",
    "        self.b = 0\r\n",
    "        self.gram = self.gram_matrix(X)\r\n",
    "\r\n",
    "        n_iter = 0\r\n",
    "        wrong = 1\r\n",
    "\r\n",
    "        while wrong > 0 and n_iter < self.max_iter:\r\n",
    "            wrong = 0\r\n",
    "            if self.shuffle:\r\n",
    "                index = np.random.permutation(X.shape[0])\r\n",
    "            else:\r\n",
    "                index = np.arange(X.shape[0])\r\n",
    "            for i in index:\r\n",
    "                x, y = X[i], Y[i]\r\n",
    "                if y * (np.sum(self.alpha * Y * self.gram[i, :]) + self.b) <= 0:\r\n",
    "                    self.alpha[i] += self.eta\r\n",
    "                    self.b += self.eta * y\r\n",
    "                    wrong += 1\r\n",
    "                    n_iter += 1\r\n",
    "\r\n",
    "                    if self.verbose:\r\n",
    "                        print('Iteration {} samples x{} was misclassified, α = {}, b = {}'.format(n_iter, i + 1, self.alpha, self.b))\r\n",
    "\r\n",
    "        self.w = self.alpha2w(X, Y)\r\n",
    "\r\n",
    "        print('Finished at iteration {}, α = {}, b = {}, w = {}'.format(n_iter, self.alpha, self.b, self.w))\r\n",
    "\r\n",
    "    \r\n",
    "    def predict(self, X):\r\n",
    "        return np.apply_along_axis(self.sign, axis=-1, arr=X)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 例题"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 例2.1\r\n",
    "&emsp;&emsp;训练数据集中，正实例点是 $x_1=(3, 3)^T$，$x_2=(4, 3)^T$，负实例点是 $x_3=(1, 1)^T$，试用感知机学习算法的原始形式求感知机模型 $f(x)=\\operatorname{sign}(w\\cdot x+b)$。这里，$w=(w^{(1)}, w^{(2)})^T$，$x=(x^{(1)}, x^{(2)})^T$。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "X = np.array([[3, 3], [4, 3], [1, 1]])\r\n",
    "Y = np.array([1, 1, -1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Iteration 1 samples x1 was misclassified, w = [3. 3.], b = 1\n",
      "Iteration 2 samples x3 was misclassified, w = [2. 2.], b = 0\n",
      "Iteration 3 samples x3 was misclassified, w = [1. 1.], b = -1\n",
      "Iteration 4 samples x3 was misclassified, w = [0. 0.], b = -2\n",
      "Iteration 5 samples x1 was misclassified, w = [3. 3.], b = -1\n",
      "Iteration 6 samples x3 was misclassified, w = [2. 2.], b = -2\n",
      "Iteration 7 samples x3 was misclassified, w = [1. 1.], b = -3\n",
      "Finished at iteration 7, w = [1. 1.], b = -3\n"
     ]
    }
   ],
   "source": [
    "p1 = Preceptron(eta=1, verbose=True)\r\n",
    "p1.fit(X, Y)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Iteration 1 samples x1 was misclassified, w = [3. 3.], b = 1\n",
      "Iteration 2 samples x3 was misclassified, w = [2. 2.], b = 0\n",
      "Iteration 3 samples x3 was misclassified, w = [1. 1.], b = -1\n",
      "Iteration 4 samples x3 was misclassified, w = [0. 0.], b = -2\n",
      "Iteration 5 samples x2 was misclassified, w = [4. 3.], b = -1\n",
      "Iteration 6 samples x3 was misclassified, w = [3. 2.], b = -2\n",
      "Iteration 7 samples x3 was misclassified, w = [2. 1.], b = -3\n",
      "Iteration 8 samples x3 was misclassified, w = [1. 0.], b = -4\n",
      "Iteration 9 samples x1 was misclassified, w = [4. 3.], b = -3\n",
      "Iteration 10 samples x3 was misclassified, w = [3. 2.], b = -4\n",
      "Iteration 11 samples x3 was misclassified, w = [2. 1.], b = -5\n",
      "Finished at iteration 11, w = [2. 1.], b = -5\n"
     ]
    }
   ],
   "source": [
    "p2 = Preceptron(eta=1, shuffle=True, verbose=True)\r\n",
    "p2.fit(X, Y)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 例2.2\r\n",
    "&emsp;&emsp;数据同例2.1，正样本点是 $x_1=(3, 3)^T$，$x_2=(4, 3)^T$，负样本点是 $x_3=(1, 1)^T$，试用感知机学习算法的对偶形式求感知机模型。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Iteration 1 samples x1 was misclassified, α = [1. 0. 0.], b = 1\n",
      "Iteration 2 samples x3 was misclassified, α = [1. 0. 1.], b = 0\n",
      "Iteration 3 samples x3 was misclassified, α = [1. 0. 2.], b = -1\n",
      "Iteration 4 samples x3 was misclassified, α = [1. 0. 3.], b = -2\n",
      "Iteration 5 samples x1 was misclassified, α = [2. 0. 3.], b = -1\n",
      "Iteration 6 samples x3 was misclassified, α = [2. 0. 4.], b = -2\n",
      "Iteration 7 samples x3 was misclassified, α = [2. 0. 5.], b = -3\n",
      "Finished at iteration 7, α = [2. 0. 5.], b = -3, w = [1. 1.]\n"
     ]
    }
   ],
   "source": [
    "p3 = Preceptron_dual(eta=1, verbose=True)\r\n",
    "p3.fit(X, Y)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAW0AAAD8CAYAAAC8TPVwAAAAOXRFWHRTb2Z0d2FyZQBNYXRwbG90bGliIHZlcnNpb24zLjMuMywgaHR0cHM6Ly9tYXRwbG90bGliLm9yZy/Il7ecAAAACXBIWXMAAAsTAAALEwEAmpwYAAAtBElEQVR4nO3deXiM5/7H8fedRYSIfQlJxFZCEiGxSxS1tJRWo7RUObW2VKW09VPtaU+1eqglRRW1VltblaqqIpXE1iQoaqt9i60UscVy//6YcCyJmTAzz8zk+7quXMlMnuV7t5eP2zPP/X2U1hohhBDOwc3oAoQQQlhOQlsIIZyIhLYQQjgRCW0hhHAiEtpCCOFEJLSFEMKJWBTaSqlCSqn5SqmdSqkdSql6ti5MCCHE/Tws3G4ssExrHaOUygPks2FNQgghsqHMLa5RShUENgPltazEEUIIQ1ky0y4HnAKmKaWqA6lAf631xTs3Ukr1BHoC5M+fP6JKlSrWrlUIIVxWamrqaa11cXPbWTLTjgTWAw201huUUmOB81rrodntExkZqVNSUnJasxBC5FpKqVStdaS57Sz5IPIIcERrvSHz9Xyg5qMUJ4QQ4uGYDW2t9XHgsFKqcuZbTYHtNq1KCCFEliy9e6QfMDvzzpF9QDfblSSEECI7FoW21nozYPZaixBCCNuSFZFCCOFEJLSFEMKJSGgLIYQTkdAWQggnIqEthBBOREJbCCGciIS2EEI4EQltIYRwIhLaQgjhRCS0hRDCiUhoCyGEE5HQFkIIJyKhLYQQTkRCWwghnIiEthBCOBEJbSGEcCIS2kII4UQktIUQwolIaAshhBOR0BZCCCcioS2EEE5EQlsIIZyIhLYQQjgRCW0hhHAiEtpCCOFEJLSFEMKJSGgLIYQT8bBkI6XUAeACcAO4rrWOtGVRQgghsmZRaGdqrLU+bbNKhBBCmCWXR4QQwolYGtoaWK6USlVK9TS7dfrJRypKCCFE1iwN7YZa65rAk8BrSqnoezdQSvVUSqUopVI4fwwOrrNqoUIIISwMba310czvJ4GFQO0stpmktY7UWkfikQfmdZUZtxBCWJnZ0FZK5VdKFbj1M9Ac2PbAnQqXgyv/wPx/wY3r1qhTCCEEls20SwJJSqk/gN+Bn7TWyx64h6c3tBoFBxIhfpgVyhRCCAEW3PKntd4HVM/xkWt0gsPrIWkUBNSGyk8+TH1CCCHuYNtb/p4cAaXCYGEvOLPfpqcSQojcwLah7ZkXnp9p+nluF7h2xaanE0IIV2f7xTVFysGzk+D4Fvh5kM1PJ4QQrsw+KyIrt4SGsbBxJmyabZdTCiGEK7LfMvbGQyAoCn6KheNb7XZaIYRwJfYLbXcPiJkKeQuZrm9fOWe3UwshhKuwb8MonxLQfjqcPQg/vApa2/X0Qgjh7Ozf5a9sPWj2IexcAms/t/vphRDCmRnTmrXeaxDcBlb8Gw6sMaQEIYRwRsaEtlLQdjwUDoL53eDCCUPKEEIIZ2PcQxDy+kKHWXDlvDSWEkIICxn75JqS1aD1aDiYBKs+NLQUIYRwBsY/biz8BYjoCmvGws6fjK5GCCEcmvGhDdDyU/CrDgv7wJl9RlcjhBAOyzFC+1ZjKaVgThe4dtnoioQQwiE5RmiD6U6SdpPgxFZYOtDoaoQQwiE5TmgDPNYCogbCpq9h4yyjqxFCCIfjWKEN0Pj/oFwj02w7bYvR1QghhENxvNB2c4fnvgLvIjD3Jbj8j9EVCSGEw3C80AbwKW5qLHXuiDSWEkKIOzhmaAME1oFm/4FdP5nu4RZCCOHAoQ1Qtw9UfQZWfgD7E42uRgghDOfYoa0UtPkcipQ39Se5cNzoioQQwlCOHdpgaiz1/CzISId53eDGNaMrEkIIwzh+aAOUrAqtx8ChtaZLJUIIkUs5R2gDVO8Akf8yPe1mx49GV/NIunbtSrly5Zg4cSIAo0aNomrVqoSFhdG0aVMOHjxo9hjjxo2jYsWKKKU4ffp0ltvs3buX8PBwfHx8HnisAwcOEBISkvOBZOHW2MLDwwkPD2fz5s1WOa4QwsR5Qhug5XAoXcN0G+Dfe42u5pGMGDGC3r17A1CjRg1SUlLYsmULMTExvPXWW2b3b9CgAStWrKBs2bLZblOhQgVDQnPEiBFs3ryZzZs3Ex4ebvfzC+HKnCu0PbxMjaXc3E1PdM+4ZPcSRowYQVxcHAADBgygSZMmAKxatYpOnTo91DEbN25Mvnz5AKhbty5Hjhwxu0+NGjUICgp6qPNl5fr163Tq1Ing4GBiYmK4dMn+/22FEOZZHNpKKXel1Cal1BJbFmRWoUBoNxlO/Gla6m7nhTdRUVEkJppuP0xJSSE9PZ1r166RmJhIdHQ0AB06dLh9eeDOr5kzZ5o9/ldffcWTTz5p0zFkZdeuXbz66qvs2LEDX19fJkyYAJj+YspqLMOHD8/2WEOGDCEsLIwBAwZw9epVew1BiFzBIwfb9gd2AL42qsVylZpB9CBI+C8E1IGIl+126oiICFJTUzl//jxeXl7UrFmTlJQUEhMTb8/A58yZ81DH/vrrr0lJSWH16tXWLNkiAQEBNGjQAIDOnTsTFxfHwIEDGT16dI6O88knn1CqVCkyMjLo2bMnn376Ke+9954tShYiV7IotJVS/kArYBgQa9OKLPX4O3AkGZYOMj1AoXS4XU7r6elJuXLlmD59OvXr1ycsLIz4+Hj27NlDcHAwYJpp79q16759Y2Nj6dKlS5bHXbFiBcOGDWP16tV4eXnZdAxZUUpl+XrAgAHEx8fft33Hjh155513aNGiBSdOnCAyMpIpU6bg5+cHgJeXF926dWPkyJG2L16IXMTSmfYY4C2gQHYbKKV6Aj0BAgMDH7kws9zc4bkp8GW0qbFUrwTwLmz782K6RDJy5EimTp1KaGgosbGxRERE3A66nM60N23aRK9evVi2bBklSpSwRckAHD16lC5durBy5cr7fnfo0CHWrVtHvXr1+Oabb2jYsCGA2Zn2L7/8ctfrtLQ0/Pz80Frzww8/WO2uFCGEidlr2kqp1sBJrXXqg7bTWk/SWkdqrSOLFy9utQIfKH8xU2Op88dgYW+4edMup42KiiItLY169epRsmRJ8ubNS1RU1EMfb9CgQaSnp9O+fXvCw8Np06bN7d9ld/dFXFwc/v7+HDlyhLCwMLp37w6YrrPf+vleaWlpeHhk/fd05cqVGT9+PMHBwZw9e5Y+ffo81Fg6depEaGgooaGhnD59mnffffehjiOEyJrSZj7IU0p9ArwEXAfyYrqm/b3WunN2+0RGRuqUlBRr1vlg6yfCsreh6XsQ9ab9zvuQunbtSuvWrYmJibHL+Xx8fEhPT2fcuHEEBgbe9ZeCEMIxKKVStdaR5rYzO9PWWg/WWvtrrYOAjsCqBwW2Ier0gmrPwqqPYH+C0dWYVbBgQYYOHXp7cY2t3FpcU7JkSQD69u0rgS2EkzM7075rY6UeBwZqrVs/aDu7z7QBrl6AyU3g8lnT9W3f0vY9vxBCPAKrzbTvpLX+zVxgG8argGnhTcZFaSwlhHBZzrUi0pwSwfB0HBxeDyv+bXQ1Qghhda4V2gBh7aFWD1g3DrYvMroaIYSwKtcLbYAWw6BMBPzwGpzeY3Q1QghhNa4Z2h5e0H4GuHuaFt5kXDS6IiGEsArXDG2AQgHw3GQ4uQOWxMoT3YUQLsF1Qxug4hPQ6G3Y8h2kTjO6GiGEeGSuHdoAjd6CCk3g57fh6EajqxFCiEfi+qHt5g7tpkD+EjD3Zbh0xuiKhBDiobl+aAPkLwrPz4ALabCwl90aSwkhhLXljtAG8I+EFh/DX8sh6TOjqxFCiIeSe0IboHYPCHkO4j+Gfb8ZXY0QQuRY7gptpUzL3ItWgvmvmPpwCyGEE8ldoQ3g5QMdZsG1yzCvqzSWEkI4ldwX2gDFK0ObODi8AX6Vh84KIZxH7gxtgNAYqN0L1k+APxcaXY0QQlgk94Y2QPOPwL8WLOoLp/8yuhohhDArd4e2Rx7Tg4E9vGCONJYSQji+3B3aAAX94bkpcGon/PiGNJYSQjg0CW0w9SZ5fDBsnQspXxldjRBCZEtC+5boQaaugMsGw9FUo6sRQogsSWjf4uYG7SaDT0lpLJVLXb58mUaNGnHjxg0OHjxIzZo1CQ8Pp1q1akycONHs/kOHDiUsLIzw8HCaN2/OsWOmxVtLlizhvfeMvbX0zrHdcv78efz9/enbt6/Z/R15bLmN0ja4hhsZGalTUlKsfly7OJIKU1tA+cfhxbmmMBe5wvjx47l+/Tr9+/cnIyMDrTVeXl6kp6cTEhLC2rVrKV26dLb7nz9/Hl9fXwDi4uLYvn07EydORGtNzZo1WbNmDfny5bPXcO5y59hu6d+/P6dOnaJIkSKMGzfugfs78thchVIqVWsdaW47SaR7+UdAy09gz6+QONLoaoQdzZ49m7Zt2wKQJ08evLy8ALh69So3LegMeSvUAC5evIhSCgClFI8//jhLliyxQdWWuXNsAKmpqZw4cYLmzZtbtL8jjy23kdDOSq3uENre1Fhq7yqjqxF2kJGRwb59+wgKCrr93uHDhwkLCyMgIIC33377gbPsW4YMGUJAQACzZ8/mww8/vP1+ZGQkiYmJtijdrHvHdvPmTd58801GjszZpMQRx5YbSWhnRSl4eqxpufuC7nDuiNEVCRs7ffo0hQoVuuu9gIAAtmzZwp49e5gxYwYnTpwwe5xhw4Zx+PBhOnXqdNclhxIlSty+Dmxv945twoQJPPXUU/j7++foOI44ttxIQjs7efLD87Pg+lVTY6nrGUZXJGzI29ubK1euZPm70qVLExISkqPZZKdOnViwYMHt11euXMHb2/uR63wY945t3bp1jBs3jqCgIAYOHMjMmTN55513LD6eI40tN5LQfpDij0Gbz+FIMvw61OhqhA0VLlyYGzdu3A63I0eOcPnyZQDOnj1LUlISlStXBqBLly78/vvv9x3jr7/+1wph0aJFVKlS5fbr3bt3ExISYsshZOvesc2ePZtDhw5x4MABRo4cSZcuXRg+fDjgfGPLjcyGtlIqr1Lqd6XUH0qpP5VSH9ijMIcR0g7q9IENE2HbAvPbC4c0ezYEBZluBgoKMr2+V/PmzUlKSgJgx44d1KlTh+rVq9OoUSMGDhxIaGgoAFu2bMny+vY777xDSEgIYWFhLF++nLFjx97+XXx8PK1atbLF0ADz47tzbA/iiGMT99BaP/ALUIBP5s+ewAag7oP2iYiI0C7l2lWtJz+h9Ud+Wp/caXQ1Ioe+/lrrfPm0NvUoMH3ly2d6/06pqam6c+fODzzWuXPndExMTI7Of/z4cd2kSZOclm0xS8bnrGPLTYAUbSaPtdY5u09bKZUPSAL6aK03ZLdd1bBwvX3L5of/m8QRnTsKX0ZBvmLQY5XpYQrCKQQFwcGD979ftiwcOHD3e1OnTuXll1/G3d3daudPTk7G09OT8PBwqx3zTpaOzxnHlptYep+2RaGtlHIHUoGKwHit9dtZbNMT6AmQp1TFiMFf/sCgFpXJ7+WR4+Id1t54mPWs6TmTz00x3WUiHJ6bW9Z9wJQCC26/dniuPr7cwqqLa7TWN7TW4YA/UFspdd+nDlrrSVrrSK11ZNH8eZi+9gAtxiSQ+NepHBfvsCo0hsZDYNt8SJ5idDXCQoGBOXvf2bj6+MTdcnT3iNb6HyAeaPmg7UoX8mZe73rk8XDjpa9+Z9C8Pzh3yUWexRj1JlRqbmosdcRJl+rnMsOGwb0rrPPlM73vClx9fOJultw9UlwpVSjzZ2+gGbDT3H61goqw9PUoXn28At9vOsoTo1ezbFvaIxdsODc3ePZLKOBnaix18W+jKxJmdOoEkyaZrvEqZfo+aZLpfVfg6uMTdzN7TVspFQbMANwxhfxcrfWHD9rn3oZR246e4635W9iedp4nQ0rxQdtqlCiQ99GrN9LRjabGUkFR0GkeuFnvwx0hRO5jtWvaWustWusaWuswrXWIucDOSkiZgizq24BBLSqzcudJmo1KYH7qEXJy54rDKVMTWg6HvSshYYTR1Qghcgm7rYj0dHfjtcYVWfp6FJVK+DBw3h+8PC2ZI2cv2asE64v8F4R1gN+Gw54VRlcjhMgF7L6MvWIJH+b2qscHbaqRcuAMzUcnMGPtAW7edMJZt1LQejQUrwILesA/h42uSAjh4gzpPeLmpni5fhDLB0QTGVSE9xf/yfNfrmPPyXQjynk0efJDh1lw45o0lhJC2JyhDaP8C+djRrdafNa+On+dTOepsYmMj9/DtRtOtiKgWCVoOw6OpsDyIUZXI4RwYYZ3+VNK8VyEPytiG/FE1RKM+GUXbcetYdvRc0aXljPVnoG6r8Hvk2DrfKOrEUK4KMND+5biBbyY0CmCiZ1rcir9Km3Hr+HTZTu5cu2G+Z0dRbMPIKAuLO4HJ83eyi6EEDnmMKF9S8sQP1YMaES7GmX44re9PDU2keQDTvJkdHdPaD/NdJ177ktw9YLRFQkhXIzDhTZAwXyejGhfnVmv1Cbjxk3aT1zHe4u2kX71utGlmedbGp77Cv7eA4tfz7qTjxBCPCSHDO1boioV55c3ounWIIhZ6w/SYnQCv+06aXRZ5pVvZGos9ef3pmvcQghhJQ4d2gD5vTx4/+lqzO9dH+887nSdlkzs3M2cvejgt9Y1jIXHWsIvQ+BwstHVCCFchMOH9i0RZQvz0+sN6dekIos3H6PZ6NUs3ZrmuEvh3dzg2Yng6wfzXoaLp42uSAjhApwmtAG8PNx5s3llFvdtiF9Bb16dvZHeX6dy8nzWT9E2nHdheH4mXDwFC7rDTSe6E0YI4ZCcKrRvqVral4Wv1mfwk1X4bdcpnhi1mrnJhx1z1l26Bjz5X9gXD6s/NboaIYSTc8rQBvBwd6NXowr83D+KKn6+vLVgCy999TuHzzhgA6qIrlD9BVj9X/hLGksJIR6e04b2LeWL+/Bdj7p89EwImw//Q/PRCUxN2s8NR2pApRS0GgUlqsL33eGfQ0ZXJIRwUk4f2mBqQNW5blmWD4imTvkifLhkO+0nruWvEw60uCVPPlNjqZs3TE+8uX7V6IqEEE7IJUL7ltKFvJnWtRZjOoSz//RFWsUl8fnKvxynAVXRCtB2PBzbCL/8n9HVCCGckEuFNpgaUD1Towy/xjaiRUgpPvt1N09/nsTWIw7SgKpqG6jX1/Q09y1zja5GCOFkXC60bynm48XnL9RgcpdIzl7KoO34JD75eYdjNKB64t8QWA9+7A8ndxhdjRDCibhsaN/SrGpJlg9oRIdaAXy5eh8txySwfp/BT1B394SYaZDHB+ZIYykhhOVcPrQBCnp78km7ML7pXoebGjpOWs+QhVu5cOWacUX5+kHMVDizFxb1lcZSQgiL5IrQvqV+xWIseyOK7g3L8e3vh2g+OoH4nQY2oCoXBU2GwvYfYMNE4+oQQjiNXBXaAPnyePBu66os6FMfHy8Puk1P5o3vNnHGqAZUDd6Ax56E5e/CoQ3G1CCEcBq5LrRvqRFYmCWvN6R/00os2ZJGs1Gr+fGPY/ZfCu/mBs9+Ab5lTA8GTj9l3/MLIZxKrg1tMDWgGtDsMZa83hD/wt70+3YTPWamcvycnRtQeRc2Lby59DcseEUaSwkhspWrQ/uWKqV8+f7VBgx5KpikPadoNmo13/5+yL6zbr/q0Gok7F8Nv31iv/MKIZyKhHYmdzdFj+jyLOsfTbUyvgz+fisvTt7Awb8v2q+Iml0gvDMkjIDdy+13XiGE0zAb2kqpAKVUvFJqu1LqT6VUf3sUZpSgYvn5pntdPn42lG1Hz9FiTAJTEvfZrwFVq5FQMhS+7wFnD9rnnEIIp2HJTPs68KbWuipQF3hNKVXVtmUZy81N8WKdQJbHRtOgQjE++mkH7b5Yy67jdlgE4+kNz88AfdP0xBtpLCWEuIPZ0NZap2mtN2b+fAHYAZSxdWGOwK+gN1NejmRsx3AOn7lE688TGbNiNxnXbdyAqmgFeOYLOLYJlr1j23MJIZxKjq5pK6WCgBrAfTcUK6V6KqVSlFIpp065zm1rSinahpfh1wHRPBXqx5gVf/H050lsPvyPbU8c3Brqvw4pU+GP72x7LiGE01CW3iGhlPIBVgPDtNbfP2jbyMhInZKSYoXyHM+K7Sd494dtnLxwhVcaliO2WWW887jb5mQ3rsPMNnB0I/RYCSWr2eY8QgjDKaVStdaR5razaKatlPIEFgCzzQW2q3uiakmWx0bTsXYgkxP303JsAmv32uhJ6+4epv4kXgVMjaWunLfNeYQQTsOSu0cU8BWwQ2s9yvYlOT7fvJ58/Gwo3/aoC8CLkzcw+PutnLdFA6oCpaD9dDh7ABa9Jo2lhMjlLJlpNwBeApoopTZnfj1l47qcQr0KRVnWP5qe0eWZk3yIZqNWs2L7CeufKKgBPPE+7FgM6ydY//hCCKdh8TXtnHDla9rZ+ePwP7y9YAs7j1+gTfXSvP90VYr6eFnvBFrDnM6wexl0/QkC61rv2EIIw1n1mrYwr3pAIRb3bciAJx7j521pPDFqNYs2H7XeUnilTM+XLBggjaWEyMUktK0oj4cb/Z+oxE+vR1G2aH76f7eZV2akcOyfy9Y5gXchU2Opy2dhwb+ksZQQuZCEtg08VrIAC/rU591Wwazde5rmoxOYveEgN62xFL5UKLT6DPYnQPywRz+eEMKpSGjbiLubontUeZa/0Ygw/4IMWbiNFyavZ/9pKzSgqtEZarwEiZ/BrmWPfjwhhNOQ0LaxwKL5mN29DsPbhbL92HlajklgUsJert94xKXwT40wzboX9jTdDiiEyBUktO1AKUXH2oH8GtuIqErF+XjpTtp9sZYdaY+wWMbTG56fBRqY2wWu2fnBDUIIQ0ho21GpgnmZ3CWCcS/W4OjZyzz9eRKjft3N1esP+YFikXLw7ERI+wN+fsu6xQohHJKEtp0ppWgdVpoVsY14unpp4lb+Reu4JDYeOvtwB6zyFDQcABtnwOZvrFusEMLhSGgbpHD+PIzuEM60rrVIv3qd575Yy4c/budSxvWcH6zxuxAUBUsGwPFt1i9WCOEwJLQN1rhKCZYPiKZTnUCmrtlPizEJrNmTwwZUtxpL5S0Ec1+CK+dsUqsQwngS2g6gQF5PPnomlDk96+Lh5kanKRt4e/4Wzl3OQQMqnxLQfprpEWXSWEoIlyWh7UDqlC/Kz/2j6NWoPPNSD9Ns1GqW/3nc8gOUrQ/NPoAdP8K6cbYrVAhhGAltB5PX053BTwbzw2sNKJI/Dz1npfLaNxs5dcHCZ0XW6wvBT8Ov78PBtbYtVghhdxLaDirMvxA/9mvIm80e49c/T9Bs9GoWbjpivgHVrcZShcvCvG5wwQatYoUQhpHQdmCe7m70a1qJn15vSLli+Rkw5w+6TU/mqLkGVHkLmhbeXDkHC14xPbZMCOESJLSdQKWSBZjfuz7vP12VDfvO0HzUamatO/DgBlSlQqD1aDiQCPEf2a9YIYRNSWg7CXc3RbcG5Vg+IJoagYUZuuhPOk5az75T6dnvFP4CRHSFpNGwc6ndahVC2I6EtpMJKJKPWa/U5r8xYew8fp6WYxP54rcHNKBq+Sn4VYeFveHMfvsWK4SwOgltJ6SU4vnIAFbENqJx5eJ8umwnz0xYw/ZjWTSg8swLz880fUA59yW4ZqUHMgghDCGh7cRK+OZlYucIJnSqyfFzV2gzLomRv+ziyrV7GlAVDoJ2k+D4Vlg6yJBahRDWIaFtRZcvX6ZRo0bcuGEKzZYtW1KoUCFat25t0f4JCQnUrFkTDw8P5s+ff/v9U6dO0bJlyyz3UUrxVKgfvw5oRNvwMoyL30OruERSD565e8PHWkDUm7BpFmz6+uEGKIQwnIS2FU2dOpV27drh7u4OwKBBg5g1a5bF+wcGBjJ9+nRefPHFu94vXrw4fn5+rFmzJtt9C+fPw2fPV2fGv2pz5dpNYiau49+L/+Ti1Ttu92s8BMpFw09vQtqWnA1OCOEQJLStaPbs2bRt2/b266ZNm1KgQAGL9w8KCiIsLAw3t/v/tzzzzDPMnj3b7DEaPVacXwZE06VuWaavPUDz0Qkk7M58crubOzw3FbwLmx6ccPkfi2sTQjgGCW0rycjIYN++fQQFBdnk+JGRkSQmJlq0rY+XBx+0DWFe73p4ebrRZervDJz3B+cuXQOf4tB+Opw7LI2lhHBCEtpWcvr0aQoVKmSz45coUYJjx47laJ9aQUVY+noUrz5egYWbjvLE6NUs25YGgXWh2X9g5xJYG2ejioUQtiChbSXe3t5cuWK75zReuXIFb2/vHO+X19Odt1pWYdFrDSju40XvrzfS5+tUTlbrBlWfgRUfwIHsr5ULIRyLhLaVFC5cmBs3blgU3IMHD2bhwoU5Ov7u3bsJCQl52PIIKVOQRX0bMKhFZVbuPEmz0YksDHgHXaQczO8GF3LQAlYIYRizoa2UmqqUOqmUkudYmdG8eXOSkpJuv46KiqJ9+/asXLkSf39/fvnlFwC2bt1KqVKl7ts/OTkZf39/5s2bR69evahWrdrt38XHx9OqVatHqs/T3Y3XGldk6etRVCrhw4BF+/g/j0HcvHIe5v9LGksJ4QSUuVafSqloIB2YqbW2aKoXGRmpU1JSrFCeg/jvf6FWLWjc+H/vxcdDcjK89b+noG/cuJHRo0ebvc2vRYsWtwPcUtHR0SxatIjChQvnaL/s3LypmbX+IJ8u28nTJPKp2zh0/f6o5h9a5fhCiJxRSqVqrSPNbWd2pq21TgDOmNvOpdWqBc8/bwpqMH1//nnT+3eoWbMmjRs3vr24Jjs5DexTp04RGxtrtcAGcHNTvFw/iOUDokkLasvX15ui1o4lbcMCq51DCGF9ZmfaAEqpIGBJrp1pw/+Cuk8f+OILmDv37pm3E9Na80PyfiotjaGsPsaiOt/SoUUjPN3lIw8h7MVqM+0cnLCnUipFKZVy6tQpax3WcTRubArs//zH9N1FAhtMS+GfrV0evx5zcXP3oOb6/rT/fBXbjspT3YVwNFYLba31JK11pNY6snjx4tY6rOOIjzfNsIcONX2/danEhRQtU5H8L0wj2O0Q/zo3nrbj1/Dpsp33N6ASQhhG/v1riVuXRubOhQ8/NH2/8xq3K6nUDBU9iDZ6FcODNvHFb3t5amwiyQdy98caQjgKS275+xZYB1RWSh1RSr1i+7IcTHLy3dewGzc2vU5ONrYuW3n8HSjfmPYnxrLwWR8ybtyk/cR1vLdoG+lX5bZAIYxk0QeROeWSH0TmNhdPw5fR4O7Jxa6rGJlwnOlrD+Dnm5dh7UJpXLmE0RUK4VLs/kGkcDH5i2U2ljpC/qV9eb9VMPN71yeflwfdpiUTO2czZy9mGF2lELmOhLbIXkBtaD4Mdi2FtWOJKFuYn15vSL8mFVn8xzGajV7NT1vSsMW/1oQQWZPQFg9WpxdUexZWfgj7E/HycOfN5pVZ3LchfgW9ee2bjfSalcrJ87ZrliWE+B8JbfFgSkGbz6FoRVN/kszGUlVL+7Lw1foMfrIKq3efoumo1cxNPiyzbiFsTEJbmOdVwPRE94x0mNcNblwDwMPdjV6NKvBz/yiC/Xx5a8EWXvrqdw79fcnggoVwXRLawjIlguHpODi0FlZ+cNevyhf34bsedfnomRA2H/6HFmMS+CppPzduyqxbCGuT0BaWC2sPtbrD2s9h++K7fuXmpuhctyzLB0RTt3wR/rNkOzET1/LXiQsGFWs7Xbt2pVy5ckycOBGAhIQEatasiYeHB/Pnz7foGOPGjaNixYoopTh9+nSW2+zdu5fw8HB8fHweeKwDBw48Uq/1O73yyitUr16dsLAwYmJiSE9Pt8pxhfVIaIucafExlIkwPV/y7733/bp0IW+mdq3FmA7hHDh9kVZxScSt/IuM6zcNKNZ2RowYQe/evQEIDAxk+vTpvPjiixbv36BBA1asWEHZsmWz3aZChQps3rz5UUvNkdGjR/PHH3+wZcsWAgMDGTdunF3PL8yT0BY54+Flun/bzR3mvAQZ91+/VkrxTI0y/BrbiBYhpRj1627ajEtiy5F/7F7uvUaMGEFcnOm5mAMGDKBJkyYArFq1ik6dOj3UMYOCgggLC8PNzfI/TjVq1LDqQ6CvX79Op06dCA4OJiYmhkuXHu5zBV9fX8DU+fHy5csopaxWo7AOCW2Rc4UCod0UOLkdfnoz2ye6F/Px4vMXajC5SyRnL2XwzPg1fLJ0B5czjGtAFRUVdfup9ikpKaSnp3Pt2jUSExOJjo4GoEOHDoSHh9/3NXPmTMPqNmfXrl28+uqr7NixA19fXyZMmACY/mLKaizDhw/P9ljdunWjVKlS7Ny5k379+tlrCMJCHkYXIJxUpSeg0Vuw+lMIrAMRXbPdtFnVktQuV4ThP+/gy4R9/PLncYY/F0bd8kXtV2+miIgIUlNTOX/+PF5eXtSsWZOUlBQSExNvz8DnzJlj97oeVUBAAA0aNACgc+fOxMXFMXDgQEaPHp3jY02bNo0bN27Qr18/5syZQ7du3axdrngEMtMWD6/R21ChCSx9C45tfuCmBb09+aRdGN90r8NNDR0nrWfIwq1cuHLNPrVm8vT0pFy5ckyfPp369esTFRVFfHw8e/bsITg4GHDOmfa9lzFuvTY3027RogXh4eF07979rv3d3d3p2LEjCxbIk4wcjcy0xcNzczddJvkyCua+BL0SwPvBj0SrX7EYy96IYtTy3Uxds59VO08y7NkQmlQpaaeiTZdIRo4cydSpUwkNDSU2NpaIiIjbQeeoM+2jR4/SpUsXVq5ced/vDh06xLp166hXrx7ffPMNDRs2BDA7077z0Xdaa/bu3UvFihXRWrN48WKqVKli3UGIRyYzbfFo8heF9jPgfBos7A03zd8lki+PB++2rsqCPvUpkNeDf01P4Y3vNnHGTg2ooqKiSEtLo169epQsWZK8efMSFRX10MdLTk7G39+fefPm0atXL6pVq3b7d+Hh4VnuExcXh7+/P0eOHCEsLOz2TDclJeW+We8taWlpeHhkPc+qXLky48ePJzg4mLNnz9KnT58cj0Nrzcsvv0xoaCihoaGkpaXx3nvv5fg4wrakNauwjg2T4OdB0PQ9iHrT4t0yrt9kfPweJvy2hwJ5Pfl3m2o8Hebn0HctdO3aldatWxMTE2OX8/n4+JCens64ceMIDAykTZs2djmvsC9pzSrsq3YPCHkOVn0E+xMs3i2PhxsDmj3Gj/0aElDYm9e/3USPmSkcP+e4DagKFizI0KFDby+usZVbi2tKljRdOurbt68EtpCZtrCiq+kwuQlcPmO6vu1bOke737ipmZq0n89+3YWnmxv/1yqYjrUCHHrWLYS1yExb2J+XD3SYZVpwc0djKUu5uyl6RJdnWf9oqpXxZfD3W3lx8gYO/n3RRgUL4XwktIV1Fa8MbeLg8HpY8e+HOkRQsfx8070uHz8byraj52gxJoHJCfukAZUQSGgLWwiNgdo9Yd04+POHhzqEm5vixTqBLI+NpmHFYgxbuoN2X6xl13HXa0AlRE5IaAvbaD4MykTCor5wes9DH8avoDeTu0QS90INDp+5ROvPExmzYrfLNaASwlIS2sI2PPKYGku5e5oW3mQ8/HVppRRtqpdmRWwjngr1Y8yKv3j68yQ2H/7HauUK4SwktIXtFAqA56bAyR2wJDbbxlKWKpI/D2M71uCrlyM5d/ka7Sas4aMl2w1tQCWEvUloC9uq2BQefwe2fAep06xyyKbBJVkeG03H2oFMSdpPizEJrN2b9YMEhHA1EtrC9qLfggpN4ee34ehGqxzSN68nHz8byrc96qIUvDh5A4O/38J5OzegEsLeJLSF7bm5QbvJkL8EzH0ZLp2x2qHrVSjKsv7R9Iouz5zkwzQbtZoV209Y7fhCOBoJbWEf+Yuanuh+IQ0W9rKosZSlvPO4M/ipYH54rQGF8+Wh+8wU+n27ib/Tr1rtHEI4CgltYT/+EdDyE/hrOSR9ZvXDh/kXYnHfhsQ2e4xl29J4YtRqFm0+ii1aNQhhFItCWynVUim1Sym1Ryn1jq2LEi6sVncIiYH4j2Hfb1Y/fB4PN15vWomfXo+ibNH89P9uM6/MSOHYP5etfi4hjGA2tJVS7sB44EmgKvCCUqqqrQsTLkopeHosFK0E81+B88dscprHShZgQZ/6DG1dlXV7/6b56ARmbzjITVkKL5ycJTPt2sAerfU+rXUG8B3Q1rZlCZfm5QMdvobrV0wfTF63zcMP3N0UrzQsxy9vRFM9oCBDFm7jhcnr2X9aGlAJ52XJ48bKAIfveH0EqHPvRkqpnkDPzJdXlVLbHr08h1QMcOWbgu08vmPQw8tuZzsIxeb2lv9/TsyVx1fZko2s9oxIrfUkYBKAUirFkr6wzsiVxwYyPmcn43NeSimLHkJgyeWRo0DAHa/9M98TQghhZ5aEdjJQSSlVTimVB+gILLZtWUIIIbJi9vKI1vq6Uqov8AvgDkzVWv9pZrdJ1ijOQbny2EDG5+xkfM7LorHZ5BmRQgghbENWRAohhBOR0BZCCCdi1dB25eXuSqmpSqmTrnr/uVIqQCkVr5TarpT6UynV3+iarEkplVcp9btS6o/M8X1gdE3WppRyV0ptUkotMboWa1NKHVBKbVVKbbb01jhnopQqpJSar5TaqZTaoZSql+221rqmnbncfTfQDNMCnGTgBa31dqucwGBKqWggHZiptQ4xuh5rU0r5AX5a641KqQJAKvCMC/3/U0B+rXW6UsoTSAL6a63XG1ya1SilYoFIwFdr3droeqxJKXUAiNRau+TCGqXUDCBRaz0l8y69fFrrf7La1pozbZde7q61TgCs1wjawWit07TWGzN/vgDswLQa1iVok/TMl56ZXy7zKbxSyh9oBUwxuhaRM0qpgkA08BWA1joju8AG64Z2VsvdXeYPfW6ilAoCagAbDC7FqjIvH2wGTgK/aq1daXxjgLcAV31MvQaWK6VSM1tmuJJywClgWublrSlKqfzZbSwfRIq7KKV8gAXAG1rr80bXY01a6xta63BMq3prK6Vc4jKXUqo1cFJrnWp0LTbUUGtdE1O30dcyL1e6Cg+gJvCF1roGcBHI9jNBa4a2LHd3cpnXehcAs7XW3xtdj61k/tMzHmhpcCnW0gBok3nd9zugiVLqa2NLsi6t9dHM7yeBhZgux7qKI8CRO/7lNx9TiGfJmqEty92dWOYHdV8BO7TWo4yux9qUUsWVUoUyf/bG9IH5TkOLshKt9WCttb/WOgjTn7tVWuvOBpdlNUqp/JkfjpN52aA54DJ3cWmtjwOHlVK3uvw1BbK9AcCaXf4eZrm701BKfQs8DhRTSh0B3tdaf2VsVVbVAHgJ2Jp53Rfg/7TWS40ryar8gBmZdzm5AXO11i53a5yLKgksNM0r8AC+0VovM7Ykq+sHzM6c8O4DumW3oSxjF0IIJyIfRAohhBOR0BZCCCcioS2EEE5EQlsIIZyIhLYQQjgRCW0hhHAiEtpCCOFE/h+9G+r0SZCgwgAAAABJRU5ErkJggg==",
      "text/plain": [
       "<Figure size 432x288 with 1 Axes>"
      ]
     },
     "metadata": {
      "needs_background": "light"
     },
     "output_type": "display_data"
    }
   ],
   "source": [
    "plt.xlim(0, 6)\r\n",
    "plt.ylim(0, 6)\r\n",
    "x = np.linspace(0, 6, 10)\r\n",
    "y1 = -(p1.w[0] * x + p1.b) / p1.w[1]\r\n",
    "y2 = -(p2.w[0] * x + p2.b) / p2.w[1]\r\n",
    "plt.plot(x, y1)\r\n",
    "plt.plot(x, y2)\r\n",
    "plt.text(3, 0.5, 'w={}, b={}'.format(p1.w, p1.b))\r\n",
    "plt.text(1, 4, 'w={}, b={}'.format(p2.w, p2.b))\r\n",
    "\r\n",
    "plt.plot(X[0, 0], X[0, 1], 'bo')\r\n",
    "plt.plot(X[1, 0], X[1, 1], 'bo')\r\n",
    "plt.plot(X[2, 0], X[2, 1], 'rx')\r\n",
    "plt.text(X[0, 0] + 0.1, X[0, 1] + 0.1, '({}, {})'.format(X[0, 0], X[0, 1]))\r\n",
    "plt.text(X[1, 0] + 0.1, X[1, 1] + 0.1, '({}, {})'.format(X[1, 0], X[1, 1]))\r\n",
    "plt.text(X[2, 0] + 0.1, X[2, 1] + 0.1, '({}, {})'.format(X[2, 0], X[2, 1]))\r\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 习题"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 习题2.1\r\n",
    "&emsp;&emsp;Minsky 与 Papert 指出：感知机因为是线性模型，所以不能表示复杂的函数，如异或 (XOR)。验证感知机为什么不能表示异或。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "解答：异或逻辑是线性不可分的，异或逻辑表为\r\n",
    "\r\n",
    "|x<sup>(1)</sup>|x<sup>(2)</sup>|x<sup>(1)</sup>⊕x<sup>(2)</sup>|   y   |\r\n",
    "| :-----------: | :-----------: | :----------------------------: | :---: |\r\n",
    "|       0       |       0       |                0               |   -1  |\r\n",
    "|       1       |       0       |                1               |   +1  |\r\n",
    "|       0       |       1       |                1               |   +1  |\r\n",
    "|       1       |       1       |                1               |   -1  |"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Finished at iteration 10000, w = [0. 0.], b = 0\n"
     ]
    },
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAYQAAAD8CAYAAAB3u9PLAAAAOXRFWHRTb2Z0d2FyZQBNYXRwbG90bGliIHZlcnNpb24zLjMuMywgaHR0cHM6Ly9tYXRwbG90bGliLm9yZy/Il7ecAAAACXBIWXMAAAsTAAALEwEAmpwYAAAQG0lEQVR4nO3df4xlZX3H8fcHlh9ZNYqygRV2WUk3RUybgrOI2jRstQmQhsWqBEIqGM1UKqkm/YeUgAmEVPnDNgYLmSARmg2yRaNriyEoY2jTQHcg/CbIQgLsZoUVGpSsxWK//eM+wOw4s/Pjnr33zu77ldycc57z3PN8H87MfPbec+4lVYUkSYcMuwBJ0mgwECRJgIEgSWoMBEkSYCBIkhoDQZIEdBAISdYkmUzyeJLHknxplj5J8o0k25M8nOTUfseVJHVrRQfHeB3426p6IMk7gPuT3FVVj0/rcxawvj0+BFzflpKkEdH3K4Sq2lVVD7T1XwFPAMfN6LYJuKV67gXelWR1v2NLkrrTxSuENyVZB5wC3Ddj13HA89O2d7S2XTOePw6MA7ztbW/74EknndRleZJ0wLv//vt/UVWrlvLczgIhyduB7wJfrqpfLuUYVTUBTACMjY3V1NRUV+VJ0kEhybNLfW4ndxklOYxeGGyuqu/N0mUnsGba9vGtTZI0Irq4yyjAt4Anqurrc3TbCnym3W10OvBKVe2ao68kaQi6eMvoo8BfAo8kebC1/R2wFqCqbgDuAM4GtgN7gM92MK4kqUN9B0JV/QeQefoU8MV+x5Ik7T9+UlmSBBgIkqTGQJAkAQaCJKkxECRJgIEgSWoMBEkSYCBIkhoDQZIEGAiSpMZAkCQBBoIkqTEQJEmAgSBJagwESRJgIEiSGgNBkgQYCJKkxkCQJAEGgiSpMRAkSYCBIElqDARJEmAgSJIaA0GSBBgIkqTGQJAkAR0FQpKbkryY5NE59p+R5JUkD7bHlV2MK0nqzoqOjvNt4Drgln30+feq+vOOxpMkdayTVwhVdQ/wchfHkiQNxyCvIXw4yUNJfpTkAwMcV5K0AF29ZTSfB4ATqurVJGcD3wfWz+yUZBwYB1i7du2ASpMkwYBeIVTVL6vq1bZ+B3BYkqNn6TdRVWNVNbZq1apBlCZJagYSCEmOTZK2flob96VBjC1JWphO3jJKcitwBnB0kh3AV4DDAKrqBuBTwCVJXgd+DZxfVdXF2JKkbnQSCFV1wTz7r6N3W6okaUT5SWVJEmAgSJIaA0GSBBgIkqTGQJAkAQaCJKkxECRJgIEgSWoMBEkSYCBIkhoDQZIEGAiSpMZAkCQBBoIkqTEQJEmAgSBJagwESRJgIEiSGgNBkgQYCJKkxkCQJAEGgiSpMRAkSYCBIElqDARJEmAgSJIaA0GSBBgIkqSmk0BIclOSF5M8Osf+JPlGku1JHk5yahfjavRs3gzr1sEhh/SWmzcPuyIt2LXXwuTk3m2Tk712HRS6eoXwbeDMfew/C1jfHuPA9R2NqxGyeTOMj8Ozz0JVbzk+bigsGxs2wHnnvRUKk5O97Q0bhluXBqaTQKiqe4CX99FlE3BL9dwLvCvJ6i7G1ui4/HLYs2fvtj17eu1aBjZuhC1beiFw5ZW95ZYtvXYdFAZ1DeE44Plp2zta216SjCeZSjK1e/fuAZWmrjz33OLaNYI2boRLLoGrr+4tDYODykhdVK6qiaoaq6qxVatWDbscLdLatYtr1wianITrr4crrugtZ15T0AFtUIGwE1gzbfv41qYDyDXXwMqVe7etXNlr1zLwxjWDLVvgqqveevvIUDhoDCoQtgKfaXcbnQ68UlW7BjS2BuTCC2FiAk44AZLecmKi165lYNu2va8ZvHFNYdu24dalgUlV9X+Q5FbgDOBo4AXgK8BhAFV1Q5IA19G7E2kP8NmqmtrXMcfGxmpqap9dJEkzJLm/qsaW8twVXRRQVRfMs7+AL3YxliRp/xipi8qSpOExECRJgIEgSWoMBEkSYCBIkhoDQZIEGAiSpMZAkCQBBoIkqTEQJEmAgSBJagwESRJgIEiSGgNBkgQYCJKkxkCQJAEGgiSpMRAkSYCBIElqDARJEmAgSJIaA0GSBBgIkqTGQJAkAQaCJKkxECRJgIEgSWo6CYQkZyZ5Msn2JJfNsv/iJLuTPNgen+9iXElSd1b0e4AkhwLfBP4M2AFsS7K1qh6f0fW2qrq03/EkSftHF68QTgO2V9UzVfUb4DvApg6OK0kaoC4C4Tjg+WnbO1rbTJ9M8nCS25Osme1AScaTTCWZ2r17dwelSZIWalAXlX8IrKuqPwTuAm6erVNVTVTVWFWNrVq1akClSZKgm0DYCUz/F//xre1NVfVSVb3WNm8EPtjBuJKkDnURCNuA9Unel+Rw4Hxg6/QOSVZP2zwHeKKDcSVJHer7LqOqej3JpcCdwKHATVX1WJKrgKmq2gr8TZJzgNeBl4GL+x1XktStVNWwa5jV2NhYTU1NDbsMSVpWktxfVWNLea6fVJYkAQaCJKkxECRJgIEgSWoMBEkSYCBIkhoDQZIEGAiSpMZAkCQBBoIkqTEQJEmAgSBJagwESRJgIEiSGgNBkgQYCJKkxkCQJAEGgiSpMRAkSYCBIElqDARJEmAgSJIaA0GSBBgIkqTGQJAkAQaCJKkxECRJQEeBkOTMJE8m2Z7ksln2H5Hktrb/viTruhhXI+baa2Fycu+2ycleu5aFzZth3To45JDecvPmYVekQeo7EJIcCnwTOAs4Gbggyckzun0O+O+q+j3gH4Cv9TuuRtCGDXDeeW+FwuRkb3vDhuHWpQXZvBnGx+HZZ6GqtxwfNxQOJl28QjgN2F5Vz1TVb4DvAJtm9NkE3NzWbwc+liQdjK1RsnEjbNnSC4Err+wtt2zptWvkXX457Nmzd9uePb12HRy6CITjgOenbe9obbP2qarXgVeA98w8UJLxJFNJpnbv3t1BaRq4jRvhkkvg6qt7S8Ng2XjuucW168AzUheVq2qiqsaqamzVqlXDLkdLMTkJ118PV1zRW868pqCRtXbt4tp14OkiEHYCa6ZtH9/aZu2TZAXwTuClDsbWKHnjmsGWLXDVVW+9fWQoLAvXXAMrV+7dtnJlr10Hhy4CYRuwPsn7khwOnA9sndFnK3BRW/8UcHdVVQdja5Rs27b3NYM3rils2zbcurQgF14IExNwwgmQ9JYTE712HRzSxd/lJGcD/wgcCtxUVdckuQqYqqqtSY4E/hk4BXgZOL+qntnXMcfGxmpqaqrv2iTpYJLk/qoaW8pzV3RRQFXdAdwxo+3Kaev/A3y6i7EkSfvHSF1UliQNj4EgSQIMBElSYyBIkgADQZLUGAiSJMBAkCQ1BoIkCTAQJEmNgSBJAgwESVJjIEiSAANBktQYCJIkwECQJDUGgiQJMBAkSY2BIEkCDARJUmMgSJIAA0GS1BgIkiTAQJAkNQaCJAkwECRJjYEgSQIMBElS01cgJHl3kruSPNWWR83R77dJHmyPrf2MKUnaP/p9hXAZ8JOqWg/8pG3P5tdV9UftcU6fY0qS9oN+A2ETcHNbvxk4t8/jSZKGpN9AOKaqdrX1nwPHzNHvyCRTSe5Ncm6fY0qS9oMV83VI8mPg2Fl2XT59o6oqSc1xmBOqameSE4G7kzxSVU/PMtY4MA6wdu3aeYuXJHVn3kCoqo/PtS/JC0lWV9WuJKuBF+c4xs62fCbJT4FTgN8JhKqaACYAxsbG5goXSdJ+0O9bRluBi9r6RcAPZnZIclSSI9r60cBHgcf7HFeS1LF+A+GrwJ8leQr4eNsmyViSG1uf9wNTSR4CJoGvVpWBIEkjZt63jPalql4CPjZL+xTw+bb+n8Af9DOOJGn/85PKkiTAQJAkNQaCJAkwECRJjYEgSQIMBElSYyBIkgADQZLUGAiSJMBAkCQ1BoIkCTAQJEmNgSBJAgwESVJjIEiSAANBktQYCJIkwECQJDUGgiQJMBAkSY2BIEkCDARJUmMgSJIAA0GS1BgIkiTAQJAkNQaCJAkwECRJTV+BkOTTSR5L8n9JxvbR78wkTybZnuSyfsaUJO0f/b5CeBT4C+CeuTokORT4JnAWcDJwQZKT+xxXktSxFf08uaqeAEiyr26nAdur6pnW9zvAJuDxfsaWJHWrr0BYoOOA56dt7wA+NFvHJOPAeNt8Lcmj+7m2YToa+MWwi9iPnN/ydiDP70CeG8DvL/WJ8wZCkh8Dx86y6/Kq+sFSB55NVU0AE23cqaqa87rEcuf8ljfnt3wdyHOD3vyW+tx5A6GqPr7Ugzc7gTXTto9vbZKkETKI2063AeuTvC/J4cD5wNYBjCtJWoR+bzv9RJIdwIeBf0tyZ2t/b5I7AKrqdeBS4E7gCWBLVT22gMNP9FPbMuD8ljfnt3wdyHODPuaXquqyEEnSMuUnlSVJgIEgSWpGJhAO9K/BSPLuJHcleaotj5qj32+TPNgeI3/xfb7zkeSIJLe1/fclWTeEMpdsAfO7OMnuaefs88OocymS3JTkxbk+75Oeb7S5P5zk1EHX2I8FzO+MJK9MO3dXDrrGpUqyJslkksfb380vzdJn8eevqkbiAbyf3gcqfgqMzdHnUOBp4ETgcOAh4ORh177A+V0LXNbWLwO+Nke/V4dd6yLmNO/5AP4auKGtnw/cNuy6O57fxcB1w651ifP7E+BU4NE59p8N/AgIcDpw37Br7nh+ZwD/Ouw6lzi31cCpbf0dwM9m+dlc9PkbmVcIVfVEVT05T7c3vwajqn4DvPE1GMvBJuDmtn4zcO7wSunMQs7H9HnfDnws83zXyQhZzj9v86qqe4CX99FlE3BL9dwLvCvJ6sFU178FzG/ZqqpdVfVAW/8VvTs4j5vRbdHnb2QCYYFm+xqMmf8RRtUxVbWrrf8cOGaOfkcmmUpyb5JzB1Paki3kfLzZp3q3IL8CvGcg1fVvoT9vn2wvyW9PsmaW/cvVcv59W6gPJ3koyY+SfGDYxSxFexv2FOC+GbsWff4G8V1Gbxrk12AMw77mN32jqirJXPf7nlBVO5OcCNyd5JGqerrrWtWZHwK3VtVrSf6K3quhPx1yTVqYB+j9vr2a5Gzg+8D64Za0OEneDnwX+HJV/bLf4w00EOoA/xqMfc0vyQtJVlfVrvay7cU5jrGzLZ9J8lN6yT+qgbCQ8/FGnx1JVgDvBF4aTHl9m3d+VTV9LjfSu1Z0oBjp37d+Tf8DWlV3JPmnJEdX1bL44rskh9ELg81V9b1Zuiz6/C23t4yW89dgbAUuausXAb/ziijJUUmOaOtHAx9ltL8mfCHnY/q8PwXcXe2K1zIw7/xmvCd7Dr33cg8UW4HPtLtVTgdemfa257KX5Ng3rmclOY3e38Nl8Y+VVve3gCeq6utzdFv8+Rv21fJpV8Q/Qe89rteAF4A7W/t7gTtmXDn/Gb1/NV8+7LoXMb/3AD8BngJ+DLy7tY8BN7b1jwCP0Lub5RHgc8OuewHz+p3zAVwFnNPWjwT+BdgO/Bdw4rBr7nh+fw881s7ZJHDSsGtexNxuBXYB/9t+9z4HfAH4Qtsfev9zq6fbz+Osd/+N6mMB87t02rm7F/jIsGtexNz+GCjgYeDB9ji73/PnV1dIkoDl95aRJGk/MRAkSYCBIElqDARJEmAgSJIaA0GSBBgIkqTm/wFAY9kHzPbFtQAAAABJRU5ErkJggg==",
      "text/plain": [
       "<Figure size 432x288 with 1 Axes>"
      ]
     },
     "metadata": {
      "needs_background": "light"
     },
     "output_type": "display_data"
    }
   ],
   "source": [
    "X = np.array([[0, 0], [0, 1], [1, 0], [1, 1]])\r\n",
    "Y = np.array([-1, 1, 1, -1])\r\n",
    "\r\n",
    "p = Preceptron(eta=1)\r\n",
    "p.fit(X, Y)\r\n",
    "\r\n",
    "plt.xlim(-1, 2)\r\n",
    "plt.ylim(-1, 2)\r\n",
    "plt.plot(X[0, 0], X[0, 1], 'rx')\r\n",
    "plt.plot(X[1, 0], X[1, 1], 'bo')\r\n",
    "plt.plot(X[2, 0], X[2, 1], 'bo')\r\n",
    "plt.plot(X[3, 0], X[3, 1], 'rx')\r\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 习题2.3\r\n",
    "&emsp;&emsp;证明以下定理：样本集线性可分的充分必要条件是正实例点集所构成的凸壳与负实例点集所构成的凸壳互不相交。设集合 $S \\subset R^n$ 是由 $R^n$ 中的 $k$ 个点所组成的集合，即 $S={x_1, x_2, \\cdots, x_k}$。定义 $S$ 的凸壳 $\\operatorname{conv}(S)$ 为\r\n",
    "$$\\operatorname{conv}(S)=\\left\\{x=\\sum_{i=1}^kλ_ix_i\\Bigg|\\sum_{i=1}^kλ_i=1, λ_i\\ge0, i=1, 2, \\cdots, k\\right\\}$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "解答：设样本集中正实例点集为 $S_+$，负实例点集为 $S_-$。\r\n",
    "\r\n",
    "**必要性**：\r\n",
    "\r\n",
    "假设样本集是线性可分的，则存在超平面 $w_{opt}\\cdot x+b_{opt}=0$ 可将 $S_+$ 和 $S_-$ 完全正确地划分到 $w_{opt}\\cdot x+b_{opt}=0$ 的两侧。存在 $ε > 0$，使所有的正实例点满足 $w_{opt}\\cdot x_i+b_{opt} > ε$，所有的负实例点满足 $w_{opt}\\cdot x_j+b_{opt} < ε$。\r\n",
    "\r\n",
    "若 $\\operatorname{conv}(S_+)$ 和 $\\operatorname{conv}(S_-)$ 相交，设 $x\\in\\operatorname{conv}(S_+)$ 且 $x\\in\\operatorname{conv}(S_-)$，$x=\\sum_{y_i=1}λ_ix_i=\\sum_{y_j=-1}λ_jx_j$，则\r\n",
    "$$w_{opt}\\cdot x+b_{opt} = w_{opt}\\cdot\\sum_{y_i=1}λ_ix_i+b=\\sum_{y_i=1}λ_i(w_{opt}\\cdot x_i+b)>ε\\sum_{y_i=1}λ_i=ε>0$$\r\n",
    "$$w_{opt}\\cdot x+b_{opt} = w_{opt}\\cdot\\sum_{y_j=1}λ_jx_j+b=\\sum_{y_j=1}λ_j(w_{opt}\\cdot x_j+b)<ε\\sum_{y_j=1}λ_j=ε<0$$\r\n",
    "矛盾！故正实例点集所构成的凸壳与负实例点集所构成的凸壳互不相交。\r\n",
    "\r\n",
    "**充分性**：\r\n",
    "\r\n",
    "假设正实例点集所构成的凸壳与负实例点集所构成的凸壳互不相交，定义两点之间的距离为\r\n",
    "$$d(x_1, x_2)=||x_1−x_2||_2$$\r\n",
    "定义 $\\operatorname{conv}(S_+)$ 和 $\\operatorname{conv}(S_-)$ 之间的距离为\r\n",
    "$$d(\\operatorname{conv}(S_+), \\operatorname{conv}(S_-))=\\min d(x_i, x_j),\\ x_i\\in\\operatorname{conv}(S_+), x_j\\in\\operatorname{conv}(S_-)$$\r\n",
    "设 $x_+\\in \\operatorname{conv}(S_+),\\ x_−\\in\\operatorname{conv}(S_-)$ 且 $d(x_+, x_−)=d(\\operatorname{conv}(S_+), \\operatorname{conv}(S_-))$。对于任意正实例点 $x$，有 $d(x, x_−)≥d(x_+, x_−)$，对于任意负实例点 $x$，有 $d(x, x_+)≥d(x_+, x_−)$。存在超平面\r\n",
    "$$w\\cdot x+b=0$$\r\n",
    "其中，\r\n",
    "$$w=x_+-x_-$$\r\n",
    "$$b=-\\frac{x_+\\cdot x_+-x_-\\cdot x_-}{2}$$\r\n",
    "对于任意正实例点 $x$，\r\n",
    "$$\\begin{align}\r\n",
    "w\\cdot x+b\r\n",
    "&=(x_+-x_-)\\cdot x-\\frac{x_+\\cdot x_+-x_-\\cdot x_-}{2}\\\\\r\n",
    "&=x_+\\cdot x-x_-\\cdot x-\\frac{x_+\\cdot x_+-x_-\\cdot x_-}{2}\\\\\r\n",
    "&=\\frac{x\\cdot x-2x_-\\cdot x+x_-\\cdot x_--x\\cdot x+2x_+\\cdot x-x_+\\cdot x_+}2\\\\\r\n",
    "&=\\frac{d^2(x, x_-)-d^2(x, x_+)}2\\\\\r\n",
    "&≥\\frac{d^2(x_+, x_-)-d^2(x, x_+)}2\\\\\r\n",
    "&≥0\r\n",
    "\\end{align}$$\r\n",
    "同理，对于任意负实例点 $x$，有 $w\\cdot x+b≤0$。故存在超平面将样本集的正实例点和负实例点完全正确地划分到超平面的两侧，样本集是线性可分的。\r\n",
    "\r\n",
    "综上，样本集线性可分的充分必要条件是正实例点集所构成的凸壳与负实例点集所构成的凸壳互不相交。"
   ]
  }
 ],
 "metadata": {
  "interpreter": {
   "hash": "2093c2be60cc259f53ede9b7cfd8c85fa59c38f3db4658dddcd5f5730d6bb867"
  },
  "kernelspec": {
   "display_name": "Python 3.8.8 64-bit ('test_py38': conda)",
   "name": "python3"
  },
  "language_info": {
   "name": "python",
   "version": ""
  },
  "orig_nbformat": 4
 },
 "nbformat": 4,
 "nbformat_minor": 2
}